package jianzhi_offer;


public class _22_二叉搜索树的后序遍历序列 {
	public boolean VerifySquenceOfBST(int [] sequence) {
		if(sequence.length == 0) return false;
        return help(sequence,0,sequence.length-1);
    }
	
	public boolean help(int[] sequence,int left,int right) {
		if (left >= right) return true;
		int i = left;
		while(sequence[i] < sequence[right]) ++i;
		for(int j=i+1;j<right-1;++j) {
			if(sequence[j] < sequence[right]) return false;
		}
		return help(sequence,left,i-1)&&help(sequence,i,right-1);
	}
}
